`
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
`

/**
 * @param {number[][]} stones
 * @return {number}
 */
var removeStones = function (stones) {
  const n = stones.length

  // 给每个石头进行编码
  const codeToId = new Map()
  for (let i = 0; i < n; i++) {
    codeToId.set(encode(stones[i]), i)
  }

  // 存储每行每列的石头
  const colIndexToCodes = new Map()
  const rowIndexToCodes = new Map()
  for (const point of stones) {
    const [x, y] = point
    if (!rowIndexToCodes.has(x)) rowIndexToCodes.set(x, [])
    if (!colIndexToCodes.has(y)) colIndexToCodes.set(y, [])
    rowIndexToCodes.get(x).push(encode(point))
    colIndexToCodes.get(y).push(encode(point))
  }

  const uf = new UF(n)

  // 把每一列的节点连通
  for (const col of colIndexToCodes.values()) {
    const firstId = codeToId.get(col[0]);
    for (let i = 1; i < col.length; i++) {
      const otherId = codeToId.get(col[i]);
      uf.union(firstId, otherId);
    }
  }

  // 把每一行的节点连通
  for (const row of rowIndexToCodes.values()) {
    const firstId = codeToId.get(row[0]);
    for (let i = 1; i < row.length; i++) {
      const otherId = codeToId.get(row[i]);
      uf.union(firstId, otherId);
    }
  }

  // 石头总数 - 连通分量数量就是被消除的石头个数
  return n - uf.count();
};

function encode(point) {
  return point[0] * 10000 + point[1]
}

class UF {
  // n 为图中节点的个数
  constructor(n) {
    // 连通分量个数
    this._count = n
    // 存储每个节点的父节点
    this.parent = Array.from({ length: n }, (_, index) => index)
  }

  // 将节点 p 和节点 q 连通
  union(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)

    if (rootP === rootQ) {
      return
    }

    this.parent[rootQ] = rootP
    // 两个连通分量合并成一个连通分量
    this._count--
  }

  // 判断节点 p 和节点 q 是否连通
  connected(p, q) {
    const rootP = this._find(p)
    const rootQ = this._find(q)
    return rootP === rootQ
  }

  // 返回图中的连通分量个数
  count() {
    return this._count
  }

  _find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this._find(this.parent[x])
    }
    return this.parent[x]
  }
}